// Source : https://oj.leetcode.com/problems/triangle/
// Author : simba
// Date   : 2016-04-03

/**********************************************************************************
*
* Given a triangle, find the minimum path sum from top to bottom.
* Each step you may move to adjacent numbers on the row below.
*
* For example, given the following triangle
*
* [
*      [2],
*     [3,4],
*    [6,5,7],
*   [4,1,8,3]
* ]
*
* The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
*
* Note:
* Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
*
**********************************************************************************/

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

func minTotal(inputTri [][]int) int {
	var minT int

	for i := 0; i < len(inputTri); i++ {
		intSort := inputTri[i]
		sort.Ints(intSort)
		minT += intSort[0]
		fmt.Print(intSort[0])
		if i != len(inputTri)-1 {
			fmt.Print(" + ")
		}
	}
	fmt.Println(" = ", minT)
	return minT
}

//随机生成最少1层、最多10层的三角形阵列
func createTriangle() [][]int {
	var row int
	s := rand.NewSource(time.Now().UnixNano())
	r := rand.New(s)
	row = r.Intn(9) + 1

	res := make([][]int, row)
	for i := 0; i < row; i++ {
		innerLen := i + 1
		res[i] = make([]int, innerLen)
		for j := 0; j < innerLen; j++ {
			s1 := rand.NewSource(time.Now().UnixNano())
			r1 := rand.New(s1)
			res[i][j] = r1.Intn(30)
			time.Sleep(1)
		}
		fmt.Println(res[i])
	}

	return res
}

func main() {
	inputTri := createTriangle()
	minTotal(inputTri)
}
